LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

XZ 45

M.Sc. DEGREE EXAMINATION – MATHEMATICS

THIRD SEMESTER – APRIL 2008

    MT 3806 – ALGORITHMIC GRAPH THEORY

 

 

 

Date : 03/05/2008            Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

Answer all questions.

1(a)(i). Obtain clique covers of size 2 and 3 for the following graph.

(OR)

(ii). Prove that an interval graph satisfies the triangulated graph property.

(5 marks)

(b)(i). State the breadth-first search algorithm. Simulate it on the following graph by  selecting the vertex a.

(ii). State the depth-first search algorithm and simulate it on the following graph by  selecting the vertex a.

(15 marks)

2(a)(i). Define a simplicial vertex. Obtain a perfect elimination scheme for the following graph

 

                                                                                    (OR)

(ii). Define a vertex separator and a minimum vertex separator. Obtain a minimum

vertex separator for the following graph.

(5 marks)

(b)(i). Let G be an undirected graph. Then prove that the following statements are equivalent.

(1). G is triangulated.

(2). Every minimal vertex separator induces a complete subgraph in G.

(ii). Prove that every triangulated graph has a simplicial vertex.

(OR)

(iii). Prove that an undirected graph is triangulated if and only if the ordering produced

by the Lexicographic breadth first search is a perfect vertex elimination scheme.

(iv). Prove that a family of subtrees of a tree satisfies the Helly property.

(10+5 marks)

 

3(a)(i). Define a split graph; prove that an undirected graph is a split graph if and only if its complement is a               split graph.

(OR)

(ii). Let G be a split graph with the vertex set partitioned into a stable set S and a clique K. If |S| = α(G)               and |K| = ω(G) – 1, then prove that there exists an x ε S such that K +{x} is a clique.

(5 marks)

(b)(i). Let G be an undirected graph. Prove that the following statements are equivalent.

(1). G is a split graph

(2). G and  are triangulated graphs

(3). G contains no induced subgraph isomorphic to 2K₂, C₄ or C₅.

(OR)

(ii). Let G be an undirected graph with degree sequence d₁ ≥ d₂ ≥ … ≥ d_n and let m = max {i : d_i ≥ i – 1}.             Then prove that G is a split graph if and only if

.

(15 marks)

4(a)(i). Define a permutation graph. Draw the permutation graph corresponding to the

permutation [7,2,5,1,6,8,3,4].

(OR)

(ii). What is a permutation labeling? Illustrate with an example.

(5 marks)

 

(b)(i). Prove that an undirected graph G is a permutation graph if and only if G and are                              comparability graphs.

(OR)

(ii). Let G be an undirected graph. Prove with usual notations that a bijection L from              V to {1, 2, 3 … n}         is a permutation labeling if and only if the mapping

,  is an injection.

(15 marks)

5(a)(i). Define a circular arc graph. Illustrate with an example.

(OR)

(ii). Obtain an interval representation of the interval graph given below.

 

(5 marks)

(b)(i). Let G be an undirected graph. Then prove that the following statements are equivalent.

(1). G is an interval graph

(2). G contains no chordless 4-cycle and its complement  is a comparability graph.

(3). The maximal cliques can be linearly ordered such that, for every

vertex v of  G the maximal cliques containing v occurs consecutively.

 

(OR)

(iii). Prove that an undirected graph G is a circular arc graph if and only if its

vertices can be circularly indexed v₁.v₂ …v_n so that for all i and j

 

(15 marks)

 

Go To Main page

 

Latest Govt Job & Exam Updates:

View Full List ...